package com.tcm.day07;

import com.tcm.day06.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 找出所有符合条件的路径
 * https://leetcode.cn/problems/path-sum-ii/?envType=problem-list-v2&envId=binary-tree
 */
public class Code06_AllTotalPathSum {

    class AllTotalPathSum{

        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            List<List<Integer>> result = new ArrayList();

            if(null == root) return result;

            List<Integer> preResult = new ArrayList();
            process(root, result, preResult, 0, targetSum);
            return result;
        }

        public void process(TreeNode node, List<List<Integer>> result, List<Integer> preResult, int preSum, int targetSum) {
            if(node.left == null && node.right == null) {
                if(node.val + preSum == targetSum) {
                    preResult.add(node.val);
                    result.add(copyList(preResult));
                    preResult.remove(preResult.size()-1);
                }
                return;
            }
            preSum = preSum + node.val;
            preResult.add(node.val);

            if(node.left != null) {
                process(node.left, result, preResult, preSum, targetSum);
            }

            if(node.right != null) {
                process(node.right, result, preResult, preSum, targetSum);
            }
            preResult.remove(preResult.size()-1);
        }

        public List<Integer> copyList(List<Integer> list) {
            List<Integer> data = new ArrayList();
            for(int i=0;i<list.size();i++) {
                data.add(list.get(i));
            }
            return data;
        }
    }

}
